package 力扣.位运算;

import java.sql.Connection;
import java.util.HashSet;
import java.util.Set;

public class 最大单词长度乘积318 {
    public static void main(String[] args) {
        String[] words = new String[]{"abcw","baz","foo","bar","xtfn","abcdef"};
//        String[] words = new String[]{"a","ab","abc","d","cd","bcd","abcd"};
//        String[] words = new String[]{"a","aa","aaa","aaaa"};
        int i = maxProduct2(words);
        System.out.println(i);
    }

    /**
     * 大致步骤：
     *      * - 先判断两个字符串是否有重复的字母  （难点）
     *      * - 若没有相同的字母，则计算字母的乘积。
     *      * - 取最大的长度
     *
     * 基础版：使用set集合来判断每个字符串中的单个字符是否有重复的
     *
     * @param words
     * @return
     */
    public static int maxProduct(String[] words) {
        int length = words.length;
        int re = 0;
        for (int i = 0; i < length-1; i++) {
            String pre1 = words[i];
            int length1 = pre1.length();
            for (int j = i+1; j <length ; j++) {
                String pre2 = words[j];
                int length2 = pre2.length();
                int flag = 0;
                Set<Character> hset = new HashSet<Character>();//使用set集合来判断每个字符串中的单个字符是否有重复的
                for (int k = 0; k <length1 ; k++) {
                     hset.add(pre1.charAt(k));
                }
                for (int k = 0; k < length2; k++) {
                    if (hset.contains(pre2.charAt(k))){
                        flag = 1;//标记有重复
                        break;
                    }
                }

//                System.out.println(t1);
                if (flag != 1){
                    //没有重复字母 然后计算乘积
                    int te =length1 * length2;
                    re = re >= te ? re : te;
                }

            }
        }
        return re;
    }

    /**
     * 解决：利用位运算。一共 26 个小写字母，而整型数一共 32 位。
     * 这里我们让`整型数的每一位`代表每一个字母 ，然后得到的一个整型数，它的前26位比特位用来表示字母（ 1 代表有这个字母，0 代表没有这个字母）。如 “abc” 使用 ‘111’ 即数字 7代替；  “abcf” 使用‘100011’ 即数字35。
     * 最后进行数字的与运算。如果哪一位相同则说明存在重复的字母，利用&运算即可。再拿“abc” 和 “abcf” 举例子 ‘111’ 和 ‘100011’ 进行与运算不为零 则说明存在相同的字母。
     * @param words
     * @return
     */
    public static int maxProduct2(String[] words) {
        int length = words.length;
        int[] ints = new int[length];
        for (int i = 0; i < length ; i++) {
            for (char c : words[i].toCharArray()){
                ints[i] |= (1 << (c - 97));//使用整型数代表word中的一个字符串
            }
        }
        int re = 0;
        for (int i = 0; i < length -1 ; i++) {//进行整型数的比较并得出最大长度
            int pre1 = ints[i];
            for (int j = i + 1; j < length; j++) {
                int pre2 = ints[j];
                if ((pre1 & pre2) == 0){//与运算
                    int te = words[i].length() * words[j].length();
                    re = re >= te ? re : te;
                }

            }
        }
        return re;
    }
}

